//【Day15】算法刷题（解题思路+详细注释）[面试题 17.09. 第 k 个数 ][424. 替换后的最长重复字符 ][438. 找到字符串中所有字母异位词 ]







/*[面试题 17.09. 第 k 个数 ]
题目描述：

有些数的素因子只有 3，5，7，请设计一个算法找出第 k个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
示例 1:
输入: k = 5
输出: 9

解题思路：
要求第K个数，而这些数只有素因子 3，5，7；

我们可以将三个素因子用数组保存起来，轮流将素因子与前K-1个数中的每一个数相乘，就可以得到第 k 个数；

当数与素因子相乘，我们可能会得到重复的数，则就需要使用内容不可重复的Set集合来去重，确定不重复再放入最小堆中存放。

最小堆的堆顶元素就是最小的数，所以只需要让堆顶元素出堆，取出来的第K个数就是前K的数中的第K个。

其实这道题在前面的刷题打卡中已经做过了，不过题目名字叫 ‘丑数’，当作复习一下…
————————————————
版权声明：本文为CSDN博主「.29.」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ebb29bbe/article/details/127082348*/


class Solution {
    public int getKthMagicNumber(int k) {
        int[] arr = new int[]{3,7,5};     //将素因子存入数组备用
        long n = 1l;                      //1是第一个数，用长整型是因为结果可能超出整形范围
        Set<Long> set = new HashSet<>();  //创建Set集合，用于排除重复的数
        //创建优先队列，默认为最小堆
        PriorityQueue<Long> que = new PriorityQueue<>();
        
        //将一个数分别与三个素因子相乘，若不重复则入最小堆
        for(int i = 1;i < k;++i){
            for(int a : arr){//将一个数分别与三个素因子相乘
                long q = n*a;//从第一个数1开始与素因子相乘
               if(set.add(q)){//若能放入set集合，说明没重复
                   que.offer(q);//入最小堆
               }
            }
            n = que.poll();     //从第二个数开始记录，直到第k个数
        } 
            return (int)n;      //转化为整形输出
        
    }
}








/*[424. 替换后的最长重复字符 ]
题目描述：

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回包含相同字母的最长子字符串的长度。
示例 1：
输入：s = “ABAB”, k = 2
输出：4
解释：用两个’A’替换为两个’B’,反之亦然。
示例 2：
输入：s = “AABABBA”, k = 1
输出：4
解释：
将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。
子串 “BBBB” 有最长重复字母, 答案为 4。

解题思路：
我们可以使用滑动窗口的思路解题：
首先将字符串转化为数组，滑动窗口的最大长度就是，窗口中的重复字符数量加上K个可替换字符数量。
将滑动窗口遍历整个字符数组，最终就能得到最长重复字符数。
具体看详细的注释与代码…
————————————————
版权声明：本文为CSDN博主「.29.」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ebb29bbe/article/details/127082348*/


class Solution {
    public int characterReplacement(String s, int k) {
        int len = s.length();
        if(len < 2) return len;
        char[] arr = s.toCharArray(); //将字符串字符存储进数组
        int left = 0; //左边界
        int right = 0;//右边界

        int[] sum = new int[26];//记录二十六个字符出现次数的数组
        int maxCount = 0;       //左右边界中间重复字符的数量
        int total = 0;          //最终重复字符的数量

        while(right < len){     //右边界最多抵达数组arr右边界
        
            ++sum[arr[right] - 'A']; //字符ASCII码相见，不同字符对应的作为下标
            //记录字符最大重复次数
            maxCount = Math.max(maxCount,sum[arr[right] - 'A']);
            //向右遍历
            right++;

            //若窗口中不重复字符的数量多于可以改变字符数k
            if((right - left) > (maxCount+k)){
                //记录的字符数量减去一
                --sum[arr[left]-'A'];
                //左边界向右移动一位才能继续扫描
                left++;
            }
            //总数就是最终窗口的长度
            total = Math.max(total,right-left);
        }
        return total;
        
    }
}







/*[438. 找到字符串中所有字母异位词 ]
题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

解题思路：
题目要求从第一个字符串中，找到第二个字符串的易位词，返回易位词开始下标。
那么我们就利用滑动窗口的思想，窗口长度为第二个字符串的长度，遍历第一个字符串，由此找到易位词。
但是仅仅遍历不足以判定易位词，我们还需要额外准备数组，以字符ASCII码值为下标，记录字符出现的次数，以此来判断窗口内字符串是否满足易位词条件。
具体实现可以看代码（注释详细）
————————————————
版权声明：本文为CSDN博主「.29.」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ebb29bbe/article/details/127082348*/



class Solution {
    public List<Integer> findAnagrams(String s, String p) {
       //集合记录易位词的开头字符下标
       List<Integer> list = new ArrayList<>();

       int Slen = s.length(); //获取字符串s长度
       int Plen = p.length(); //获取字符串p长度

       //如果字符串s长度比字符串p短，比可能存在易位词，返回空集合；
       if(Slen < Plen)
       return list;

       char[] cs = s.toCharArray();
       char[] cp = p.toCharArray();

       //使用数组记录窗口内字符出现次数
       int[] S = new int[26]; 
       int[] P = new int[26]; 

       

       //字符范围是“a-z”,将出现字符减去‘a’，的Ascii码之差作为下标，节省内存
       for(int i = 0;i < Plen;++i){
           //记录字符串p每个字符出现次数
           //同时记录字符串 窗口（与字符串p长度相等）内每个字符出现次数
           ++S[cs[i]-'a'];
           ++P[cp[i]-'a'];
       }
       //记录的两个数组比较，若相等，说明窗口内是易位词，记录开头下标0
       if(Arrays.equals(S,P))
       list.add(0);

       //遍历字符串s，窗口一个字符一个字符往后扫描
       for(int i = 0;i < (Slen-Plen);++i){
           //窗口向后移动一格
           --S[cs[i]-'a'];
           ++S[cs[i+Plen]-'a'];

           //若相等，说明窗口内是易位词，记录易位词开头下标
           if(Arrays.equals(S,P))
           list.add(i+1);
       }
       return list;
    }
}







